Міністерство освіти і науки
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
до лабораторної роботи № 2
з дисципліни: “Алгоритми та методи обчислень”
на тему: “ Розробка та дослідження ефективності
методів пошуку даних ”
Львів – 2016
Мета роботи
• Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
Загальне завдання:
Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць.
Список вхідних слів довжиною n=28 задати у вигляді текстового файла data.txt . Файл data.txt має містити таку інформацію (всі слова (або числа) записуються латинськими літерами підряд через кому):
прізвище, ім'я, побатькові,
день, місяць,рік народження,
назва компанii мобільного зв'язку,
підряд через пробіл всі цифри мобільного телефона, починаючи з кода оператора (всього 10 цифр),
назва області, міста і вулиці в адресі прописки,
номер будинку і квартири в адресі прописки,
абревіатура інститута, кафедри, групи,
день, місяць,рік виконання лабораторної роботи.
Наприклад: Вміст файлу data.txt :
Petrenko,Bogdan,Sergyjovuch,25,3,1989,Kyivstar,0,6,7,5,7,6,4,9,2,1,Lvivska,Lviv,Bandery,12,1,IKTA,EOM,KI-21,12,4,2010
Весь вхідний список слів розмістити в першій хеш-таблиці розмірністю m=37, метод побудови якої вибрати згідно з варіантом. Також весь вхідний список слів розмістити у другій хеш-таблиці, метод побудови якої вибрати самостійно. Забороняється вибирати хеш-функції, що співпадають з прикладами хеш-функції, наведених в цих методичних вказівках. При виборі хеш-функції намагатись, щоб ефективність організації другої таблиці була вищою, ніж першої.
Забезпечити виконання програмою на вимогу користувача операцій додавання та вилучення елементів з хеш-таблиць.
В процесі роботи з таблицями на вимогу користувача програма повинна виводити на екран вміст кожної хеш-таблиці.
Під час пошуку слів в хеш-таблицях програма повинна виводити на екран послідовність слів з якими виконуються порівняння і кількість виконаних операцій порівняння.
Лістинг програми:
CashTable.h
#include "Node.h"
#include <time.h>
#include <vector>
#include <list>
class CashTable
{
public:
CashTable(int Size);
~CashTable();
Node* Find(string Key);
bool Add(string Key, Node* node);
bool Delete(string Key);
void Print();
private:
int hesh_helper(string Key);
private:
int m_iSize;
vector<vector<Node*>> m_vTable;
};
Node.h
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <iostream>
using namespace std;
class Node
{
public:
Node(string Name, string LastName, string Number);
Node(const Node &nd);
~Node();
void SetName(string name);
string GetName();
void SetLastName(string LastName);
string GetLastName();
void SetNumber(string Number);
string GetNumber();
void print();
private:
string m_sName;
string m_sLastName;
string m_sNumber;
};
CashTable.cpp
#include "CashTable.h"
CashTable::CashTable(int Size)
{
m_iSize = Size;
m_vTable.resize(m_iSize);
}
CashTable::~CashTable()
{
for (int i = 0; i < m_vTable.size(); i++)
for (int j = 0; m_vTable[i].size(); j++)
{
if (m_vTable[i][j] != NULL)
{
delete m_vTable[i][j];
m_vTable[i][j] = NULL;
}
}
}
Node* CashTable::Find(string Key)
{
int tmp = hesh_helper(Key);
for (int i = 0; i < m_vTable[tmp].size(); i++)
{
if (m_vTable[tmp][i]->GetNumber() == Key)
{
return m_vTable[tmp][i];
}
}
return NULL;
}
bool CashTable::Add(string Key, Node* node)
{
if (Find(Key)==NULL)
...
